Implementations of the claimed invention generally may relate to decoding variable length codes and, more particularly, to decoding Huffman or similar entropy codes.
Electronic data, including text, graphics, voice, multimedia, and other strings of symbols, may be represented by binary codes. Binary coded data may be compressed in an effort to accurately represent the data while using as few bits as possible, thereby reducing the resources required for storing and/or transmitting the data. Binary codes of different or variable lengths may be used to represent different symbols in a bitstream of data. According to some binary code compression techniques, more frequently occurring symbols within a bitstream are represented with shorter codes, and less frequently occurring codes are represented using longer codes. Such a scheme may be referred to as Variable Length Coding (VLC).
One type of VLC scheme may involve Huffman codes. Huffman codes may be used, for example, in digital video compression and information retrieval for video coding standards such as Microsoft™ Windows Media, MPEG-2, MPEG-4, H.263, H.264, and other such standards employing VLC. In some implementations of Huffman codeword decoding, a bitstream segment of the incoming bitstream may be matched against the contents of a Look-Up-Table (LUT) according to a “nibble-by-nibble” approach. For example, a decoder may look into a first, fixed size nibble and try to match with first table entries in a Huffman decoding table. If no match is found, the decoder may look into a second, fixed size nibble and try to match with second table entries, and so forth. Such an approach may be conceptualized as a hashing function.
For longer Huffman codewords (e.g., 23 bit maximum), however, such nibbling schemes may take up to 6 steps and/or clocks to match the longest Huffman codewords. Longer codewords, in such a nibbling scheme, may limit decoding throughput. Such a scheme may also consume an undesirable amount of memory space for its Huffman decoding table.